import { BinTree } from './BinTree'

const bt: BinTree = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4,
      left: null,
      right: null,
    },
    right: {
      val: 5,
      left: null,
      right: null,
    },
  },
  right: {
    val: 3,
    left: {
      val: 6,
      left: null,
      right: null,
    },
    right: {
      val: 7,
      left: null,
      right: null,
    },
  },
}

/**
 * 二叉树先序遍历
 * @param root 根节点
 * @returns void
 */
/* const preorder = (root: BinTree | null): void => {
  // 如果节点为空，则退出
  if (!root) {
    return
  }
  console.log(root.val)
  preorder(root.left)
  preorder(root.right)
} */

/**
 * 非递归版本
 */
const preorder = (root: BinTree | null): void => {
  // 如果节点为空，则退出
  if (!root) {
    return
  }
  // 入栈
  const stack: BinTree[] = [root]
  // 当stack存在元素时
  while (stack.length) {
    // 出栈
    const n = stack.pop()
    console.log(n?.val)
    // 由于栈是后进先出，所以先压右子树进去
    if (n?.right) {
      stack.push(n.right)
    }
    if (n?.left) {
      stack.push(n.left)
    }
  }
}

preorder(bt)
